//#define _CRT_SECURE_NO_WARNINGS 2
//
//#include<stdio.h>
//#include<stdbool.h>
//#include<stdlib.h>
//#include<assert.h>
//
//typedef char datatype;
//
//typedef struct Stack {
//    int capacity;
//    int top;
//    datatype* arr;
//}Stack;
//
//void StackInit(Stack* st) {
//    st->capacity = 0;
//    st->top = 0;
//    st->arr = NULL;
//}
//
//void StackPush(Stack* st, datatype val) {
//    assert(st);
//    if (st->top == st->capacity) {
//        st->capacity = st->capacity == 0 ? 4 : st->capacity * 2;
//    }
//    st->arr = (datatype*)realloc(st->arr, st->capacity * sizeof(datatype));
//    if (!st->arr) {
//        perror("st->arr fail realloc");
//        return;
//    }
//    st->arr[st->top++] = val;
//}
//
//bool StackEmpty(Stack* st) {
//    assert(st);
//    return st->top == 0;
//}
//
//void StackPop(Stack* st) {
//    assert(st);
//    assert(!StackEmpty(st));
//    st->top--;
//}
//
//datatype StackTop(Stack* st) {
//    assert(st);
//    assert(!StackEmpty(st));
//    return st->arr[st->top - 1];
//}
//
//void StackDestroy(Stack* st) {
//    assert(st);
//    free(st->arr);
//    st->arr = NULL;
//    st->top = 0;
//    st->capacity = 0;
//}
//
//bool isValid(char* s) {
//    Stack st;
//    StackInit(&st);
//    while (*s) {
//        if (*s == '(' || *s == '{' || *s == '[') {
//            StackPush(&st, *s);
//        }
//        else {
//            if (StackEmpty(&st)) {
//                StackDestroy(&st);
//                return false;
//            }
//
//            datatype top = StackTop(&st);
//            if (*s == ')' && top != '(' || *s == ']' && top != '[' || *s == '}' && top != '{') {
//                StackDestroy(&st);
//                return false;
//            }
//            else {
//                StackPop(&st);
//            }
//        }
//        ++s;
//    }
//    StackDestroy(&st);
//    return true;
//}
//
//int main() {
//    char s[] = "()";
//    bool ret= isValid(s);
//    if (ret) {
//        printf("true\n");
//    }
//    else {
//        printf("false\n");
//    }
//    return 0;
//}




#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

typedef struct Node {
    int val;
    struct Node* next;
}Node;

typedef struct Queue {
    int size;
    Node* front;
    Node* rear;
}Queue;

void QueueInit(Queue* pq) {
    assert(pq);
    pq->size = 0;
    pq->front = NULL;
    pq->rear = NULL;
}

void QueuePush(Queue* pq, int x) {
    assert(pq);
    Node* newnode = (Node*)malloc(sizeof(Node));
    if (!newnode) {
        perror("newnode fail malloc");
        return;
    }
    newnode->val = x;
    newnode->next = NULL;
    if (pq->size == 0) {
        pq->front = pq->rear = newnode;
    }
    else {
        pq->rear->next = newnode;
        pq->rear = newnode;
    }
    pq->size++;
}

bool QueueEmpty(Queue* pq) {
    assert(pq);
    return pq->size == 0;
}

void QueuePop(Queue* pq) {
    assert(pq);
    assert(!QueueEmpty(pq));
    if (pq->size == 1) {
        free(pq->front);
        pq->front = pq->rear = NULL;
    }
    else {
        Node* next = pq->front->next;
        free(pq->front);
        pq->front = next;
    }
    pq->size--;
}

int QueueFront(Queue* pq) {
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->front->val;
}

int QueueRear(Queue* pq) {
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->rear->val;
}

int QueueSize(Queue* pq) {
    assert(pq);
    return pq->size;
}

void QueueDestroy(Queue* pq) {
    assert(pq);
    Node* cur = pq->front;
    while (cur) {
        cur = cur->next;
        free(pq->front);
        pq->front = cur;
    }
    pq->front = pq->rear = NULL;
    pq->size = 0;
    pq = NULL;
}

typedef struct {
    Queue* q1;
    Queue* q2;
} MyStack;


MyStack* myStackCreate() {
    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
    if (obj == NULL) {
        perror("obj fail malloc");
        return NULL;
    }
    obj->q1 = (Queue*)malloc(sizeof(Queue));
    obj->q2 = (Queue*)malloc(sizeof(Queue));
    QueueInit(obj->q1);
    QueueInit(obj->q2);
    return obj;
}

void myStackPush(MyStack* obj, int x) {
    assert(obj);
    if (obj->q1) {
        QueuePush(obj->q1, x);
    }
    else {
        QueuePush(obj->q2, x);
    }
}

bool myStackEmpty(MyStack* obj);

int myStackPop(MyStack* obj) {
    assert(obj);
    assert(!myStackEmpty(obj));
    Queue* empty = obj->q1;
    Queue* notempty = obj->q2;
    if (!QueueEmpty(obj->q1)) {
        empty = obj->q2;
        notempty = obj->q1;
    }
    int size = QueueSize(notempty);
    while (size > 1) {
        int val = QueueFront(notempty);
        QueuePop(notempty);
        QueuePush(empty, val);
        --size;
    }
    int ret = QueueFront(notempty);
    QueuePop(notempty);
    --size;
    return ret;
}

int myStackTop(MyStack* obj) {
    assert(obj);
    assert(!myStackEmpty(obj));
    Queue* empty = obj->q1;
    Queue* notempty = obj->q2;
    if (!QueueEmpty(obj->q1)) {
        empty = obj->q2;
        notempty = obj->q1;
    }
    return QueueRear(notempty);
}

bool myStackEmpty(MyStack* obj) {
    assert(obj);
    return QueueEmpty(obj->q1) &&
        QueueEmpty(obj->q2);
}

void myStackFree(MyStack* obj) {
    QueueDestroy(obj->q1);
    QueueDestroy(obj->q2);
    obj->q1 = NULL;
    obj->q2 = NULL;
    free(obj);
    obj = NULL;
}
 

int main() {
    MyStack* st;
    st = myStackCreate();
    myStackPush(st, 1);
    myStackPush(st, 2);
    myStackPush(st, 3);
    myStackPush(st, 4);
    myStackPush(st, 5);
    myStackPush(st, 6);

    return 0;
}